COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input paper.tex
C00012 00003	Mail from RAND-UNIX rcvd at 7-Nov-78 1626-PST
C00016 00004	∂18-Nov-78  1848	DBL  	Caching  
C00027 00005	\NNSECP{Acknowledgements}
C00030 ENDMK
C⊗;
\input paper.tex

\TITL{COGNITIVE  ECONOMY}

\vfill

\AUTHO{Douglas B. Lenat, \ Stanford University}

\AUTHO{Frederick Hayes-Roth, \ Rand Corporation}

\AUTHO{Phil Klahr, \ Rand Corporation}

\vfill

\vskip 10pt plus 2pt

\NNSECP{ABSTRACT}
       Intelligent systems can explore only tiny subsets of their potential
       external and conceptual worlds.   They must develop efficient  forms
       of  representation,  access,   and  operation   to  increase   their
       capacities.  Some of these  forms involve abstraction, caching,  and
       expectation- simplified processing.  These capabilities in turn  can
       combine to provide extremely powerful increases in performance.  For
       example, all three can combine to simplify simulation or, one of its
       related functions, detection of surprising events.  Our analysis  of
       the economic principles  of modern  AI systems  or (presumably  more
       sophisticated)  human  intelligence  suggests  that  previous  ideas
       regarding cognitive efficiency have erred in fundamental ways.   For
       example, the  nonredundant  storage of  properties  in  hierarchical
       inheritance nets  increases many  processing costs  while  providing
       minimal storage cost  savings.  We  propose methods  to exploit  the
       potential advantages of both schemes.

\vfill

\eject

\NSECP{INTRODUCTION}

\SSEC{Introduction}

\SSSEC{Outline}

	Our model of intelligent system organization
		Concepts, heuristics, PDIS
	Our model of intelligence:  knowledge and its expansion (through
		experimentation, discovery, conjecture, conditioning)
	Our model of computing:
		Cheap storage, expensive knowledge acquisition, limited
		computing cycles
	The problem:
		Want to develop initial systems quickly and then have
		them speed up and economize their computing to maximize
		their potential
	The principal ideas:
		Abstraction
		Caching
		Expectation-simplified computing
			e.g., ignoring expcted data
			   giving priority to surprising data
			   feeding back to confirmed/disconfirmed predictions
	Outline of the rest of the paper


2.  Abstraction
	Desirability of being able to compute rough answers cheaply
	Conceptual hierarchies
	Heuristic Hierarchies
	Interpretation and planning at levels of abstraction
		Eg., rules of bomber simulation at difft levels
		(this example will ultimately be used to suggest
		 caching for simplification)
	Related research

3.  Caching
	Modifying memory to save computed results to speed subsequent accesses
	Generalization of hardware concept
	EURISKO types of caching, as first examples
	Contrast with psychological conjectures of cognitive economy
		(e.g., Collins&Quillian, KRL, ...).  More like HR↑2 Plasticity
		model of storing all retrieved paths as direct links
	General principles
	    Updating Principles
	    -------------------

	       When

	       Why

	       How
		  get demon traps that flag the cache as out of date
		  the user requests updating if the cache seems staleness
	       Where

	       In what form

	       What

	       When not to

	       How to


	    Storage Principles
	    ------------------

	       When
		  Every time you have to call a lower order function to eval. it
		    & it took quite a while.
		  You've caled it before, recently & the value didn't change.

	       Why
		  Cost of recomputing vs. cost of storage.
		  Context of subsequent cals is similar enough (e.g.l, the same
		    arguments will come up again.

	       How
		  Called functions might suggest how to cache their value in higher
		    calling caches (e.g., my value changes often so cache my defn.).
		  Cache should be transparent & discardable (should be able to throw
		    them all away if space needed).

	       Where

	       In what form
		  value     )  what level of abstraction (partially evaluated
		  expression)    symbolic expression)

		  Stack previous values to enable you to tell if they're changing.

	       What
		  You store a flag saying you've been here before.
		  When it was computed.
		  How much effort was expended on it, down to what levels of
		    algorithms, with what around caches incorporated.
		  Certainty of the result.

	       When not to
		  The value changes too frequently.
		  The function evaluates as fast as the caching mechanism itself
		  Space is too tight

	       How to eliminate caches
		  Space tight--> eliminate last used caches (last referenced)

4.  Expectation
	Central notion:  reserve your computing for opportunities to realize
		potential for expanding knowledge
	You may decide how much to expend re-confirming the expected
	Reductions realizable through expectations:
		Perceptual set:  see what you expect with less effort
		Surprise:  heighten sensitivity to data inconsistent with
			expectations
		Predict and prepare
	What mechanisms are implicated?
		Caching
		PDMs (as triggers or demons)
	Relevance to learning
		Confirm or disconfirm predictors
		This requires setting up PDMs to fire on dis/confirmation

\SSSEC{Cognitive economy revisited}

5.  Cognitive economy revisited
	Sample problem:  using a world model (simulator) to answer questions
		(e.g., what'd happen if 100 bombers went in there?)
		Representation of this knowledge as PDMs at difft levels of abstn
		Ability to generalize and cache results at one level at the
			next higher level,
				e.g. either as numerical tables, stat. distns, or
				symbolic expressions
		Ability to answer some questions appropriately for the requestor
			at a high level of abstraction

	KB Design
		One good reason to use inheritanc is to speed knowledge
			implementation, not computing performance
		Using the system should result in its speedup
		Storage should be cheap
	Machine architecture
		PDI should be cheap
		PDMs should be scheduled with variable resources and
			should be able to spend effort accordingly
		How could propagation of changes be made efficient?
 6-Nov-78 10:55:54-PST,1738;000000000001
Mail from RAND-UNIX rcvd at 7-Nov-78 1626-PST
From: Klahr at Rand-Unix
Date:  7 Nov 1978 at 1628-PST
Message-Id: <[Rand-Unix] 7-Nov-78 16:28:14.klahr>
To: rick
cc: lenat @ sumex-aim
Subject: Joint IJCAI paper


Rick,

	Based on an initial scan of your outline, I think it looks
great.  Some preliminary thoughts:

     1. Title:  Cognitive Economy in Artificial Intelligent Systems

     2. Abstraction:  I don't think we should delve into the military
		domain of bomber simulations for the IJCAI paper.  It
		may turn off alot of people.  The hearts domain may
		similarly turn off a different group.  However, since
		we'll have examples from EURISKO, examples from hearts
		should provide an additional example domain and will
		not look central to the ideas presented.  The area of
		abstraction in simulations is powerful as we are, and
		will, experience.  This is perhaps worthy of its
		own paper.  If we do want to talk about abstraction
		in simulations, I suggest alternative domains, eg,
		ship or air traffic control, sporting events (football
		strategies), international terrorism (more people
		sympathetic here), appointment scheduling (as in proposal),
		etc.

     3. Caching:  looks good.

     4. Expectation-simplified processing:  This is a confusing phrase.
		The only alternative I can think of now is expectation-
		focusing.  The economy here is in terms of subsequent
		analysis of good/bad consequences.  Expectation-focusing
		directs the analysis and diagnosis of behavior to those
		heuristics that were instrumental in the resulting behavior.
		Demons can be generated by heuristics to fire when the
		heuristics' expectations are met/rejected.  Thus demons
		economize here by pinpointing heuristics that impacted
		the resulting behavior.

     5. The idea of forming and storing symbolic expressions deserves to
		be a fourth independent cognitive economy.  I feel it
		is much more than a simple cache.  Forming these expressions
		may involve considerable pattern-matching, deductions, etc.
		The resulting expression incorporates more than a simple
		evaluation (such as caching functional values).  In fact,
		I would consider it to involve learning as well as caching.
		The expressions are really meta-evaluations.


I think the paper would be a significant contribution to IJCAI.  I will
be happy to participate in it.

--Phil
∂18-Nov-78  1848	DBL  	Caching  
Rick and Phil,

Thanks for the notes.  I like Rick's outline, and have some comments
on it and on Phil's remarks as well.


First, title and authors.  In some sense this is not important, but
pragmatically it can have a big impact on the way a paper is received.
How about just Cognitive Economy?  This enables the paper and its
concepts to be referred to tersely, and will pique the curiosity of
many potential readers.  "Economics" sounds too presumptuous for the
material we have; the longer titles Phil suggests are more precise but
unwieldy.                 For author order, I would like to go first,
but if there is dissention we can draw lots or something.  The primary
author should have the brunt of the task of preparing the article,
in any case, including content, prose, and document preparation.


The thesis that Rick states is much too strongly worded for my taste;
co-authoring with Rick is always a pleasure because he's the only
person as brash as I -- and occasionally moreso!  But I really don't
want to claim that we have  the final set of three keys (abstrac.,
caching, expectation-simplified processing) to represenational economy.
In fact, can we think of more?

THESIS:  As often happens when I read Rick's stuff, I misunderstood it the
first time through, and as a result got an additional good idea out
of it that Rick didn't intend:

Much of what goes on today at the fore of AI can be viewed as
"expectation-simplified processing": frames, scripts, user modelling,
caching of all levels and flavors,...    Here are a few poins on the
continuum:
     After computing a value, cache it.  Note: "value" may be a number,
	a vector of numbers, an alphanumeric identifier, a vector of them...
     Synthesize a function capable of efficiently computing desired values,
        and cache that function.
     Synthesize a whole concept data structure (frame, script...) which
        contains relevant partial models of the recent situation.
There are more intermediate ones, but you see the progression from
static to dynamic, from scalar to descriptive.  In all cases, the
motivation for doing this storage is (i) speed up the recognition of
(the need to do) similar computations in the future, and (ii) speed up
or even eliminate those computations when you decide they ARE relevant
and you want the values they would return.  These are the two uses of
scripts, but also of cached constants (e.g., caching the value returned
by OWNED-BY, a function from CARS to PEOPLE). A better example: user models,
as they range from a single number, to a few numbers (e.g., in PARRY),
to a dynamic concept-modelling scheme.


OUTLINE:  

Introduction: 
 Model of sys. org. should include, perhaps, agenda-like control capabilities
 Model of intell. should stress the fact that knowledge acrretes, but only
   	occasionally shrinks (abandoning of a whole system of thought is
     	quite a rare event indeed.    --- ask Kuhn!)
 Model of computing can then, if we add the above 2 points, include this one:
  The half-frame problem
    In which the reasons supporting the tasks have the form "stiuation X is
  	not yet attained, but executing me will help you get there"
    	(e.g., facet f of concept C has only 2 entries)
    Then at task-choosing time, if a task's reasons are out-of-date, it is
 	most likely that that is because some of them are no longer valid,
	hence that the rating of the task will DECREASE
    So, all we need do is re-evaluate the top task, get a new LOWER number
	for its priority, reinsert it into the agenda, etc., and continue
	until the top task remains at the top.  The half-frame problem
	gets its name from  he fact that we do have to reevaluate some
   	tasks to see how the world has changed out from under them, BUT
	in general we need only do this for a small number of tasks to find
	the best one, not for ALL the tasks.
 Idea of Expec.: another point is that expectations allow us to set up
	frames in which to interpret the data, thereby making it v. quick.

Abstraction
 As you know, I would like to rpesent heur. hier. as a kind of conceptual hier.
 I liked the idea of using bomber simulation, and will comment again on this.

Caching
 Brian Smith (MIT grad student) gave me the general idea that the lisp EVAL
 function should, in general, have a second argument: the interpreter to use.
 One very special case of this is where EVAL takes as its second argument
 just a resource limit (time/space to expend); Bobrow and Norman discussed
 an idea like this a while back.  The continuum here stretches from the extreme
 of GETP (i,e, if a value is stored or cached there, fine, if not give up),
 to a more sophisticated inheritance search (accepting caches), 
 to the same thing but rejecting caches, to an even more complex deduction,
 perhaps with searching disk allowed, and finally to INduction (try to
 discover concepts relevant to answering the request).

 The various headings Rick suggests are interrelated, and this may cause
 us some trouble later, esp. if we don't watch out for it.  E.g., the
 updating principles constrain and are constrained by the storage ones;
 When you store is constrained by Why; etc.

Expectation
 As stated above, generalize this enough to include stereotyping,
 of events (scripts), of situations (frames), of people (user models),...

Cognitive econ. revisited
 This was quite good.
 What about the future, when processor costs drop way beolow storage, though?

Phil's comments --- comments on them:

generally I ageed.  

The heuristic about "better talk about Hearts, not Bombers", is so
ivory tower as to be fit material for Sat. Night Live.  Unfortunately,
you are right that a good many AI researchers may feel that way.  We don't,
so the hell with them.  I did like your counterproposal about int'l.
terrorism, and I agree that we won't find ANY pro-terrorists at IJCAI.

Expectation-simplified processing IS awkward, but the concise replacements
generally have very negative connotations (e.g., stereotyping).
Expectation-focusing is not much better than the origianl term, in my opinion.


Let's get together and talk more about this.  One alternative to that
would be for someone, e.g. me, to flesh out the outline, essentially
start writing some prose.

I am quite encouraged and think this will turn into a good paper.
Doug

\NNSECP{Acknowledgements}

I owe a  great debt of thanks to  many people, both for the  input of
new ideas and for the evaluation, channelling, and pruning of my own.

Let me begin by alphabetically thanking my thesis committee: Bruce Bu\-chan\-an,
Ed  Fei\-gen\-baum,  Cor\-dell   Green,  Don   Knuth,  and  Allen   New\-ell.
In\-ter\-act\-ing with each of them has been an exciting experience, and my
research has greatly benefited from their guidance.

The following individuals have each 
informally supplied some ideas or comments that appear within this
book. They all have earned my gratitude, and have significantly improved
the experence you are about to have, that of reading this book:
Danny Bobrow,
Paul Cohen,
Avra Cohn,
Randy Davis,
Bob Floyd, 
Carl Hewitt,
Bernard Meltzer,
Donald Michie,
Nils Nilsson,
Earl Sacerdoti, 
Herb Simon,
and Terry Winograd.

This research relied heavily upon the sophisticated computing environments
provided by
SAIL,
SRI, SU\-MEX, and XE\-ROX-PARC.

Around this point in the \4Acknowledgements\1,  most books and theses have some
sort of tribute to the author's wife. Until I was in the throes of
this research,  I  never fully  appreciated  the importance  of  such
support.   So  let me  sincerely acknowledge  the indispensable  aid I
received  from Merle,  my wonderful  wife, who  put up  with inverted
schedules and who gave me the confidence to tackle  this problem and
the enthusiasm to keep going.


\vfill\end